// distribution.cpp: 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#pragma comment (lib,"json_vc71_libmtd.lib")
#include <iostream>
#include<cstdlib>
#include <fstream>
#include<cstring>
#include <functional>
#include "json.h"
#include "matching.h"
using namespace std;
struct Heap
{
	int last;
	int maxsize;
	int *heap;
};
int s_time0[5000][7][7] = { 0 };//学生时间表
int timeISok(int stu_t[7][7], string d_t[], int size);
	int numOFsame(string array1[], int size1, string array2[], int size2);
	unsigned int BKDR_Hash(char *str);
	unsigned int d_NameHash(string s);
	Heap *MaxHeapInit(int HeapSize);
	void HeapInsert(int x, Heap *H, int *s_score);
	int DeleteMin(Heap *H, int *s_score);
	int find_Max_tags(int *tags, int size);
	Json::Value make_distribution_bytags(Json::Value jsroot);
int main()
{
	Json::Reader jsreader;
	// Json::Value是一种很重要的类型，可以代表任意类型。如int, string, object, array...   
	
	Json::Value jsroot;
	Json::Value jsout;
	cout << "which arithmetic(1,2)" <<endl;
	int way = 0;
	cin >> way;
	cout << "filesname(sxxx-dxx)"<<endl;
	string input;
	cin >>input;
	std::ifstream is;//is用于打开json文件
	is.open("./test/"+input+"-in.json", std::ios::binary);
	if (jsreader.parse(is, jsroot))//将jsroot与is匹配
	{
		if (way==2)jsout = heatmatching(jsroot);
		else if (way==2)jsout = make_distribution_bytags(jsroot); 
	}
	is.close();
	ofstream os;
	os.open("./test/"+input+"-out.json");
	Json::StyledWriter sw;
	os << sw.write(jsout);
	os.close();
	return 0;
}
int timeISok(int stu_t[7][7], string d_t[], int size)
{
	for (int i = 0; i<size; i++)
	{
		string w = d_t[i];
		int wi;
		if (w[0] == 'M')	wi = 0;
		else if (w[0] == 'T')
		{
			if (w[1] == 'u')	wi = 1;
			else if (w[1] = 'h')	wi = 3;
			else;
		}
		else if (w[0] == 'W')	wi = 2;
		else if (w[0] == 'F')	wi = 4;
		else if (w[0] == 'S') {
			if (w[1] == 'a')	wi = 5;
			else if (w[1] == 'u')	wi = 6;
			else;
		}
		int begin = int(w[4] - '0') * 10 + int(w[5] - '0'), end = int(w[10] - '0') * 10 + int(w[11] - '0');
		for (int j = begin + 1; j<end; j = j + 2)
		{
			if (stu_t[wi][(j - 8) / 2] == 0)
				return 0;
		}
	}
	return 1;
}
void sTimeAdd(string s_available_schedule[],int size, int s_time[7][7])
{
	for (int i = 0; i<size; i++)
	{
		string w = s_available_schedule[i];
		int wi;
		if (w[0] == 'M')	wi = 0;
		else if (w[0] == 'T')
		{
			if (w[1] == 'u')	wi = 1;
			else if (w[1] = 'h')	wi = 3;
			else;
		}
		else if (w[0] == 'W')	wi = 2;
		else if (w[0] == 'F')	wi = 4;
		else if (w[0] == 'S') {
			if (w[1] == 'a')	wi = 5;
			else if (w[1] == 'u')	wi = 6;
			else;
		}
		int begin = int(w[4] - '0') * 10 + int(w[5] - '0'), end = int(w[10] - '0') * 10 + int(w[11] - '0');
		for (int j = begin + 1; j<end; j = j + 2)
		{
			s_time[wi][(j - 8) / 2] = 1;
		}
	}
}
void sTimeOperation(int stu_t[7][7], string d_t[], int size)
{
	for (int i = 0; i<size; i++)
	{
		string w = d_t[i];
		int wi;
		if (w[0] == 'M')	wi = 0;
		else if (w[0] == 'T')
		{
			if (w[1] == 'u')	wi = 1;
			else if (w[1] = 'h')	wi = 3;
			else;
		}
		else if (w[0] == 'W')	wi = 2;
		else if (w[0] == 'F')	wi = 4;
		else if (w[0] == 'S') {
			if (w[1] == 'a')	wi = 5;
			else if (w[1] == 'u')	wi = 6;
			else;
		}
		int begin = int(w[4] - '0') * 10 + int(w[5] - '0'), end = int(w[10] - '0') * 10 + int(w[11] - '0');
		for (int j = begin + 1; j<end; j = j + 2)
		{
			stu_t[wi][(j - 8) / 2] = 0;
		}
	}
}
int numOFsame(string array1[],int size1, string array2[], int size2)
{
	int num = 0;
	bool swap = false;//标识变量，表示两种情况中的哪一种
	int end = size1;
	for (int i = 0; i < end;) {
		swap = false;//开始假设是第一种情况
		for (int j = i; j < size2; j++) { //找到与该元素存在相同的元素，将这个相同的元素交换到与该元素相同下标的位置上
			if (strcmp(array1[i].c_str(), array2[j].c_str()) == 0) { //第二种情况，找到了相等的元素
				string tmp = array2[i];//对数组2进行交换
				array2[i] = array2[j];
				array2[j] = tmp;
				swap = true;//设置标志
				num++;
				break;
			}
		}
		if (swap != true) { //第一种情况，没有相同元素存在时，将这个元素交换到尚未进行比较的尾部
			string tmp = array1[i];
			array1[i] = array1[--end];
			array1[end] = tmp;
		}
		else
			i++;
	}
	//结果就是在end表示之前的元素都找到了匹配，而end元素之后的元素都未被匹配
	return num;
}
unsigned int BKDR_Hash(char *str)
{
	unsigned int seed = 131313; // 31 131 1313 13131 131313 etc..
	unsigned int hash = 0;

	while (*str)
	{
		hash = hash * seed + (*str++);
	}

	return (hash & 0x7FFFFFFF);
}
unsigned int d_NameHash(string s)
{
	char *str = (char*)s.data();
	char jd = 0;
	unsigned int key;
	string again[5] = { "National Association for blowing music"
		,"DV Society"
		,"Table tennis association"
		,"Wushu Association"
		,"Tennis association" };
	for (int i = 0; i<5; i++)
	{
		if (again[i] == s)
		{
			jd = i + 1;
		}
	}

	if (jd)
	{
		key = (3 + jd);
	}
	else key = BKDR_Hash(str);
	unsigned int where = key % 1000;
	return where;
}
Heap *MaxHeapInit(int HeapSize)
{
	Heap *H = new Heap;
	H->maxsize = HeapSize;
	H->heap = new int[HeapSize];
	H->last = 0;
	return H;
}
void HeapInsert(int x, Heap *H,int *s_score)
{
	int i;
	if (H->last == H->maxsize) cout << "Heap is full";
	i = ++H->last;
	while (i != 1 && s_score[H->heap[i / 2 - 1]]>s_score[x] /*xyless(H->heap[i / 2 - 1], x,root)*/)
	{
		H->heap[i - 1] = H->heap[i / 2 - 1];
		i /= 2;
	}
	H->heap[i - 1] = x;
}
int DeleteMin(Heap *H,int *s_score)
{
	int i, ci;
	int x, y;
	if (H->last == 0) cout << "Heap is empty";
	x = H->heap[0];
	y = H->heap[--H->last];
	i = 1; ci = 2;
	while (ci <= H->last)
	{
		if (ci<H->last&& s_score[H->heap[ci]] > s_score[H->heap[ci - 1]]/*xyless(H->heap[ci - 1], H->heap[ci],root)*/) ci++;
		if (s_score[H->heap[ci - 1]] > s_score[y]/*xyless(H->heap[ci - 1], y,root)*/) break;
		H->heap[i - 1] = H->heap[ci - 1];
		i = ci;
		ci *= 2;
	}
	H->heap[i - 1] = y;
	return x;
}
int find_Max_tags(int *tags, int size)
{
	int tmp = 0;
	int where = 0;
	for (int i = 0; i<size; i++)
	{
		if (tmp<tags[i])
		{
			tmp = tags[i];
			where = i;
		}
	}
	return where;
}
Json::Value make_distribution_bytags(Json::Value jsroot)
{
	int d_hash_map[1000] = {0};//部门名称的hash表
	Heap *s_MaxHeap = MaxHeapInit(5000);//学生的绩点最大堆
	
	string *d_event_schedules[100];//各部门的活动时间

	string *d_department_tags[100];//各部门的兴趣标签
	
	int s_d_tags[5000][5] = { 0 };//学生兴趣与各部门兴趣相同项的数目
	
	char matched_department[100]= {0};//部门已招人数
	char *matched_student;
	Json::Value jsout;
	int *s_score;
	int departments_size = jsroot["departments"].size();//记录部门数目
	for (int i = 0; i < departments_size; i++)
	{
		Json::Value i_department = jsroot["departments"][i];
		string val_department_name = i_department["department_name"].asString();
		d_hash_map[d_NameHash(val_department_name)] = i;//为部门名称建立hash表
		
		int event_schedules_size = i_department["event_schedules"].size();
		d_event_schedules[i]= new string[event_schedules_size];
		for (int j = 0; j < event_schedules_size; j++)
			d_event_schedules[i][j] = i_department["event_schedules"][j].asString();//获取该部门的活动安排
		
		int department_tags_size = i_department["department_tags"].size();
		d_department_tags[i] = new string[department_tags_size];
		for (int j = 0; j < department_tags_size; j++)
			d_department_tags[i][j] = i_department["department_tags"][j].asString();//获取该部门的兴趣标签
		
	}

	int students_size = jsroot["students"].size();//记录学生数目
	s_score=new int[students_size];
	matched_student = new char[students_size];
	for (int i = 0; i < students_size; i++)
	{
		s_score[i] = jsroot["students"][i]["score"].asInt();
	}
	
	for (int i = 0; i < students_size; i++)
	{//取出一个学生
		Json::Value i_students = jsroot["students"][i];//取出该学生的全部信息
		
		int available_schedule_size = i_students["available_schedule"].size();
		string *s_available_schedule = new string[available_schedule_size] ;
		for (int j = 0; j < available_schedule_size; j++)
			s_available_schedule[j] = i_students["available_schedule"][j].asString();//获取该学生的空余时间
		int size0 = available_schedule_size;
		sTimeAdd(s_available_schedule, size0, s_time0[i]);
		
		int student_tags_size = i_students["student_tags"].size();
		string *s_tags = new string[student_tags_size];
		for (int j = 0; j < student_tags_size; j++)
			s_tags[j] = i_students["student_tags"][j].asString();//获取该学生的兴趣标签
		
		int departments_wish_size = i_students["departments_wish"].size();//获得该学生的部门意愿数
		string *i_departments_wish = new string[departments_wish_size];
		for (int j = 0; j < departments_wish_size; j++)//记录合适的部门以及对该部门的兴趣程度
		{
			string d_wish = i_students["departments_wish"][j].asString();
			int id_d = d_hash_map[d_NameHash(d_wish)];
			Json::Value id_department = jsroot["departments"][id_d];
			//判断时间是否合适
			if (timeISok(s_time0[i],d_event_schedules[id_d], jsroot["departments"][id_d]["event_schedules"].size()))
			{
				s_d_tags[i][j] = 0;
				continue;
			}
			//记录感兴趣程度
			s_d_tags[i][j]= numOFsame(d_department_tags[id_d], int(id_department["department_tags"].size()), s_tags, student_tags_size);
		}
		
		
	}
	for (int l = 0; l<2; l++)
	{
		for (int i = 0; i < students_size; i++)
		{	HeapInsert(i,s_MaxHeap,s_score);
		}
	for (int i = 0; i < students_size; i++)
	{
		int stu=DeleteMin(s_MaxHeap,s_score);//取出堆中成绩最好的学生
		
		Json::Value stu_students = jsroot["students"][stu];
		int max_s_d=find_Max_tags(s_d_tags[stu],5);//得到该学生最感兴趣的部门在学生意愿中的位置
		int max_d = d_NameHash(stu_students["departments_wish"][max_s_d].asString());//获得该部门的在全部部门中的位置
		max_d = d_hash_map[max_d];
		int d_member_limit = jsroot["departments"][max_d]["member_limit"].asInt();
		while (matched_department[max_d] >= d_member_limit && d_member_limit&&s_d_tags[stu][max_s_d])
		{//当部门人数满是查找下一个最感兴趣的部门
			s_d_tags[stu][max_s_d] = 0;
			max_s_d = find_Max_tags(s_d_tags[stu], 5);
			max_d = d_hash_map[d_NameHash(stu_students["departments_wish"][max_d].asString())];
			d_member_limit = jsroot["departments"][max_d]["member_limit"].asInt();
		}
		if (s_d_tags[stu][max_s_d] == 0 || d_member_limit==0) //没有找到匹配的部门，该学生加入为匹配的学生中
			matched_student[stu] = 0;
		else
		{//找到匹配的部门，并更改部门已招人数,以及修改学生时间表
			matched_department[max_d]++;
			s_d_tags[stu][max_s_d] = 0;
			sTimeOperation(s_time0[stu], d_event_schedules[max_d], jsroot["departments"][max_d]["event_schedules"].size());
			matched_student[stu] = 1;
			string d_name= jsroot["departments"][max_d]["department_name"].asString();
			string s_name = stu_students["student_name"].asString();
			jsout["matched_department_view"][d_name].append(s_name);
			jsout["matched_student_view"][s_name].append(d_name);
		}
	}
	}
	for (int i = 0; i <departments_size; i++)
	{
		if (matched_department[i]==0)
		{
			jsout["standalone_departments"].append(jsroot["departments"][i]["department_name"].asString());
		}
	}
	for (int i = 0; i <students_size; i++)
	{
		if (!matched_student[i])
		{
			jsout["standalone_students"].append(jsroot["students"][i]["student_name"].asString());
		}
	}
	return jsout;
}